翻訳と辞書 Words near each other ・ Arithmetic logic unit ・ Arithmetic mean ・ Arithmetic number ・ Arithmetic of abelian varieties ・ Arithmetic overflow ・ Arithmetic progression ・ Arithmetic rope ・ Arithmetic shift ・ Arithmetic surface ・ Arithmetic topology ・ Arithmetic underflow ・ Arithmetic variety ・ Arithmetic zeta function ・ Arithmetica ・ Arithmetica Universalis ・ Arithmetical hierarchy ・ Arithmetical ring ・ Arithmetical set ・ Arithmetico-geometric sequence ・ Arithmetic–geometric mean ・ Arithmetization of analysis ・ Arithmeum ・ Arithmomania ・ Arithmometer ・ Ariti ・ Aritmija ・ Aritmija (novel) ・ Arito Station ・ Aritomo ・ Aritomo Gotō Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Arithmetical hierarchy ： ウィキペディア英語版 Arithmetical hierarchy In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical. The arithmetical hierarchy is important in recursion theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic. The Tarski-Kuratowski algorithm provides an easy way to get an upper bound on the classifications assigned to a formula and the set it defines. The hyperarithmetical hierarchy and the analytical hierarchy extend the arithmetical hierarchy to classify additional formulas and sets. == The arithmetical hierarchy of formulas == The arithmetical hierarchy assigns classifications to the formulas in the language of first-order arithmetic. The classifications are denoted $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ for natural numbers ''n'' (including 0). The Greek letters here are lightface symbols, which indicates that the formulas do not contain set parameters. If a formula $\backslash phi$ is logically equivalent to a formula with only bounded quantifiers then $\backslash phi$ is assigned the classifications $\backslash Sigma^0\_0$ and $\backslash Pi^0\_0$. The classifications $\backslash Sigma^0\_n$ and $\backslash Pi^0\_n$ are defined inductively for every natural number ''n'' using the following rules: *If $\backslash phi$ is logically equivalent to a formula of the form $\backslash exists\; n\_1\; \backslash exists\; n\_2\backslash cdots\; \backslash exists\; n\_k\; \backslash psi$, where $\backslash psi$ is $\backslash Pi^0\_n$, then $\backslash phi$ is assigned the classification $\backslash Sigma^0\_$. *If $\backslash phi$ is logically equivalent to a formula of the form $\backslash forall\; n\_1\; \backslash forall\; n\_2\backslash cdots\; \backslash forall\; n\_k\; \backslash psi$, where $\backslash psi$ is $\backslash Sigma^0\_n$, then $\backslash phi$ is assigned the classification $\backslash Pi^0\_$. Also, a $\backslash Sigma^0\_n$ formula is equivalent to a formula that begins with some existential quantifiers and alternates $n-1$ times between series of existential and universal quantifiers; while a $\backslash Pi^0\_n$ formula is equivalent to a formula that begins with some universal quantifiers and alternates similarly. Because every formula is equivalent to a formula in prenex normal form, every formula with no set quantifiers is assigned at least one classification. Because redundant quantifiers can be added to any formula, once a formula is assigned the classification $\backslash Sigma^0\_n$ or $\backslash Pi^0\_n$ it will be assigned the classifications $\backslash Sigma^0\_m$ and $\backslash Pi^0\_m$ for every ''m'' greater than ''n''. The most important classification assigned to a formula is thus the one with the least ''n'', because this is enough to determine all the other classifications. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Arithmetical hierarchy」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.